package com.ding.practice.algorithm.leetcode.hot100;

import java.util.HashMap;


/**
 *
 * 力扣热题100之和为 K 的子数组
 * @ID = 560
 * @date 2024年07月18日13:47:25
 * 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
 *
 * 子数组是数组中元素的连续非空序列。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,1,1], k = 2
 * 输出：2
 * 示例 2：
 *
 * 输入：nums = [1,2,3], k = 3
 * 输出：2
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 2 * 104
 * -1000 <= nums[i] <= 1000
 * -107 <= k <= 107
 */
public class SubarraySum_560 {

    // 前缀和+hash表
    /*
    解题关键：理解前缀和，比如有数组 1，2，3，4，5，6。  要想求得3，4，5的和，可以用1，2，3，4，5的和减去1，2的和

    知道了解题关键，那么就很简单了
    用hash表Key作为前缀和的值，value作为出现这个前缀和的次数
    然后一步步根据大前缀和去计算需要的小前缀，详见具体算法
     */
    public int subarraySum(int[] nums, int k) {
        int ret = 0;
        HashMap<Integer,Integer> preSumMap = new HashMap();
        int sum = 0;
        preSumMap.put(0, 1);
        for(int index = 0; index < nums.length; index ++){
            // 得到前缀和
            sum = sum + nums[index];

            // 判断是否存在符合条件的前缀和
            /*
            注意这里，举例：前十的和为A，前二十的和为B，想要求得十到二十的值，为K = B-A，故想要寻找的A为B - K，即sum - k
             */
            if(preSumMap.containsKey(sum - k)){
                ret = ret + preSumMap.get(sum - k);
            }

            // 维护前缀和map，下一次比较永远这这个map的后面进行，所以可以只循环一次就好
            if(preSumMap.containsKey(sum)){
                int count = preSumMap.get(sum);
                count++;
                preSumMap.put(sum, count);
            }else {
                preSumMap.put(sum, 1);
            }

        }
        return ret;
    }




    // 自己的解法，用滑动窗口去计算和，然后符合条件的cont加1就行，时间复杂度为on2，不太好
    public int subarraySum2(int[] nums, int k) {

        int rp = 0;
        int ret = 0;
        for(int index = 0; index < nums.length; index ++){
            int sum = 0;
            rp = index;
            while(rp < nums.length){
                sum = nums[rp] + sum;
                if(sum == k){
                    ret++;
                }
                rp++;
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        SubarraySum_560 subarraySum_560 = new SubarraySum_560();
        int[] p = {1,2,3};
        System.out.println(subarraySum_560.subarraySum(p,3));
    }

}
